package leetcode_day._2022._202209._2130;

/**
 * 面试题 17.09. 第 k 个数
 * 算法：多指针 + 动态规划
 *
 * @author yzh
 * @version 1.0
 * @date 2022/9/28 23:12
 */
public class _28_面试题1709 {

    public int getKthMagicNumber(int k) {
        int[] dp = new int[k + 1];
        dp[1] = 1;
        for (int i3 = 1, i5 = 1, i7 = 1, idx = 2; idx <= k; idx++) {
            int a = dp[i3] * 3, b = dp[i5] * 5, c = dp[i7] * 7;
            int min = Math.min(a, Math.min(b, c));
            if (min == a) ++i3;
            if (min == b) ++i5;
            if (min == c) ++i7;
            dp[idx] = min;
        }
        return dp[k];
    }

}
